package org.chengn.level_middle.context1670;

import java.util.Deque;
import java.util.concurrent.LinkedBlockingDeque;

public class Context1670 {

    static class FrontMiddleBackQueue {
        Deque<Integer> front = new LinkedBlockingDeque<>();
        Deque<Integer> back = new LinkedBlockingDeque<>();

        public FrontMiddleBackQueue() {

        }

        public void pushFront(int val) {
            front.addFirst(val);
            while (front.size() - back.size() >= 1) {
                back.addFirst(front.pollLast());
            }
        }

        public void pushMiddle(int val) {
            front.addLast(val);
            while (front.size() - back.size() >= 1) {
                back.addFirst(front.pollLast());
            }
        }

        public void pushBack(int val) {
            back.addLast(val);
            while (back.size() - front.size() >= 2) {
                front.addLast(back.pollFirst());
            }
        }

        public int popFront() {
            while (back.size() - front.size() >= 1) {
                front.addLast(back.pollFirst());
            }
            if (!front.isEmpty()) {
                return front.pollFirst();
            }
            return !back.isEmpty() ? back.pollFirst() : -1;
        }

        public int popMiddle() {
            while (back.size() - front.size() >= 1) {
                front.addLast(back.pollFirst());
            }
            return !front.isEmpty() ? front.pollLast() : -1;
        }

        public int popBack() {
            while (front.size() - back.size() >= 0) {
                back.addFirst(front.pollLast());
            }
            return back.pollLast();
        }
    }
}
